package org.example.DataStructure.LinkList;

//利用循环链表解决约瑟夫问题
public class JosephText {
    public static void main(String[] args) {
        //记录首节点
        Node<Integer> head = null;
        //记录当前节点的前一个节点
        Node<Integer> pre = head;
        //构建循环链表初始化41个节点
        for (int i = 0; i < 41; i++) {
            Node<Integer> current = new Node<>(i);
            current.next = null;
            //第一个节点的插入方式
            if (i == 0) {
                head = current;
                pre = head;
                continue;
            }
            //如果不是第一个节点的插入方式
            pre.next = current;
            pre = current;
            //如果是最后一个节点，需要让最后一个节点的next变为第一个节点
            if (i == 40) {
                current.next = head;
            }
        }
        //构建count计数器，到3则删除该节点
        int count = 0;
        //遍历循环链表
        //记录当前节点
        Node<Integer> current = head;
        //记录当前节点的前一个节点
        Node<Integer> before = null;
        while (current.next != current) {
            //模拟报数
            //判断报数是不是3,当前节点后移让before变成当前节点
            if (count++ != 3) {
                before = current;
                current = current.next;
            } else {
                //如果是3则删除该节点,打印该节点,重置count
                before.next = current.next;
                System.out.print(current.data + " ");
                count = 1;
                current = current.next;
            }
        }
        //打印最后一个元素
        System.out.println(current.data);
    }

    //创建节点内部类
    private static class Node<T> {
        //数据域
        T data;
        //指针域
        Node<T> next;

        //构造方法
        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
}
